#include <iostream>

template <typename T>
struct ListNode
{
    T data;
    ListNode<T> *next = nullptr;
};

template <typename T>
class Lists
{
public:
    Lists()
    {
    }

    // 1.初始化
    ListNode<T> *getNewNode(T data)
    {
        ListNode<T> *node = new ListNode<T>;
        node->data = data;
        node->next = nullptr;
        return node;
    }

    // 2.销毁
    void destroyList()
    {
        if (header_->next == nullptr)
            return;
        ListNode<T> *tmp_node = header_->next;
        while (tmp_node != nullptr)
        {
            ListNode<T> *tmp = tmp_node;
            tmp_node = tmp_node->next;
            delete tmp;
        }
        header_->next = nullptr;
    }

    // 3.尾插
    void insertPushBack(T data)
    {
        ListNode<T> *node = getNewNode(data);
        ListNode<T> *tmp = header_;
        while (1)
        {
            if (tmp->next != nullptr)
            {
                tmp = tmp->next;
            }
            else
            {
                tmp->next = node;
                break;
            }
        }
    }

    void frontInsert(T data)
    {
        ListNode<T> *tmp = header_;
        ListNode<T> *node = getNewNode(data);
        if (tmp->next == nullptr)
            tmp->next = node;
        else
        {
            tmp = header_->next;
            header_->next = node;
            node->next = tmp;
        }
    }

    void printLists()
    {
        ListNode<T> *tmp = header_;
        while (1)
        {
            if (tmp == header_ && tmp->next != nullptr)
            {
                tmp = tmp->next;
                continue;
            }
            if (tmp->next != nullptr)
            {
                std::cout << "data:" << tmp->data << std::endl;
                tmp = tmp->next;
            }
            else if (tmp != header_)
            {
                std::cout << "data:" << tmp->data << std::endl;
                break;
            }
            else
            {
                break;
            }
        }
    }

    // 查找第一个相符的元素
    int findVal(int val)
    {
        ListNode<T> *tmp = header_;
        while (tmp != nullptr)
        {
            if (tmp->data == val)
            {
                std::cout << "find val:" << tmp->data << std::endl;
                return 1;
            }
            else
            {
                tmp = tmp->next;
                continue;
            }
        }

        if (tmp == nullptr)
        {
            std::cout << "not find val" << std::endl;
            return 0;
        }
    }

    // 反转链表
    void reverseList()
    {
        ListNode<T> *cur = header_->next;
        ListNode<T> *pre = nullptr;

        while (cur != nullptr)
        {
            ListNode<T> *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }

        header_->next = pre;
    }

    // 旋转连表
    void moveLists(int k)
    {
        // 1.计算链表长度
        ListNode<T> *tmp = header_->next;
        size_t count = 0;
        while (tmp != nullptr)
        {
            count++;
            tmp = tmp->next;
        }
        std::cout << "链表长度:" << count << std::endl;
        // 防止K大于链表长度
        k = k % count;

        if(k == 0)
            return;
        std::cout << "旋转次数:" << k << std::endl;
        size_t step = count - k;
        // 遍历链表。
        ListNode<T>* start = header_->next;
        ListNode<T> *end = header_->next;
        for(size_t i = 1; i < step; i++)
        {
            end = end->next;
        }

        while (end->next !=nullptr)
        {
            start = start->next;
            end = end->next;
        }

        tmp = header_->next;
        header_->next = start->next;
        start->next = nullptr;
        end->next = tmp;
        
    }

private:
    ListNode<T> *header_ = new ListNode<T>;
};

int main()
{
    Lists<int> lists;
    lists.insertPushBack(1);
    lists.insertPushBack(2);
    lists.insertPushBack(3);
    std::cout << "输出列表:" << std::endl;
    lists.printLists();
    lists.destroyList();
    std::cout << "输出列表:" << std::endl;
    lists.printLists();
    lists.frontInsert(1);
    lists.frontInsert(2);
    lists.frontInsert(3);
    lists.printLists();
    lists.findVal(2);
    lists.findVal(4);

    lists.reverseList();
    lists.insertPushBack(4);
    lists.insertPushBack(5);

    lists.printLists();
    lists.moveLists(2);
    lists.printLists();

    return 0;
}